package _06_动态规划;

public class _1137_第N个泰波那契数 {

    public static void main(String[] args) {

        _1137_第N个泰波那契数 v = new _1137_第N个泰波那契数();

        System.out.println(v.tribonacci(4));

    }

    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n < 3) return 1;
        int first = 0;
        int second = 1;
        int three = 1;
        for (int i = 3; i <= n; i++) {
            three = first + second + three;
            int temp = second;
            second = three - first - second;
            first = temp;
        }
        return three;
    }

}
